A conventional Wallace tree employs booth recoding to multiply, for example, a 6-bit number A by a 6-bit number B to generate a 12-bit sum S and a 12-bit carry C. Sometimes the product A.times.B equals the sum of the sum S and carry C (C+S) such as in the following longhand multiplication. For clarity, commas are placed every four digits.
______________________________________ 00,0001 (1) A .times. 01,0001 (17) B 0000,0000,0001 (1) first partial product 0000,0000,0000 (0) second partial product + 0000,0001,0000 (16) third partial product 0000,0001,0001 (17) sum S + 0000,0000,0000 (0) carry C 0000,0001,0001 (17) A .times. B = C + S ______________________________________
However, sometimes A.times.B does not equal C+S as in the following multiplication.
______________________________________ 00,0001 (1) A .times. 00,1010 (10) B 1111,1111,1110 (-2) first partial product + 1111,1111,1100 (-4) second partial product 0000,0001,0000 (16) third partial product 0000,0001,0010 (18) sum S + 1111,1111,1000 (4088) carry C 1,0000,0000,1010 (4106) S + C ______________________________________
The above sum S+C can be interpreted as having a value of 4106 unsigned or -4088 in twos complement.
Conventionally, sum S and carry C are subsequently added in an adder having an output bit length the same as the bit lengths of sum S and carry C (e.g., 12 bits). The most significant carry-out bit is discarded so that the above sum S+C has a +10 value.